package greedy;

import java.util.Arrays;
import java.util.Comparator;



class 无重叠区间_435_重做版 {
    public int eraseOverlapIntervals(int[][] intervals) {
        // 想找最少删除的  转化为能放下最多的LIS
        // 按照右边界排序  始终找左边界比右边界大的下一个 能让右边界最小
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
        int end = intervals[0][1];
        int count = 1;
        for(int i = 1; i < intervals.length; i++) {
            if(end <= intervals[i][0]) {
                end = intervals[i][1];
                count ++;
            }
        }
        return intervals.length - count;
    }
}
/**
 * 首个区间就是所有可以选择的区间中右端点最小的那个区间
 * 然后找与首个区间不重合且右边界最小的区间
 * 每个最小子问题就是这个
 * 因而直接对右边界排序
 * 按照右边界从小到大排序  双指针  当前元素左边界比cur右边界大不相交  cur  = 当前  否则都要去掉
 */
public class 无重叠区间_435 {
    public int eraseOverlapIntervals(int[][] intervals) {
        int count = 0, skip = 1;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[1] > b[1]) return 1;
                return -1;
            }
        });
        for (int i = 1, cur = 0; (cur < intervals.length - 1) && (i < intervals.length); i++) {
            if (intervals[cur][1] > intervals[i][0]) {
                count++;
                skip++;
            } else {
                cur += skip;
                skip = 1;
            }
        }
        return count;
    }

    // 也可以动态规划   和最长递增子序列_300 一样  n个区间   从1到n  找 1到i中 if(dp[i]左边界 > dp[j]右边界 ) dp[i] = Max(dp[j] + 1, dp[i])
    public int eraseOverlapIntervals_dp(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });

        int n = intervals.length;
        int[] f = new int[n];
        Arrays.fill(f, 1);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (intervals[j][1] <= intervals[i][0]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }
        return n - Arrays.stream(f).max().getAsInt();
    }
}